﻿using System;
using System.Collections.Generic;
using System.Text;

namespace ThresholdModeling
{
    public class BigInteger
    {
        private byte _numericBase = 2;
        private List<byte> _binary = new List<byte>();

        #region Constructor
        public BigInteger()
        {

        }

        public BigInteger(byte basement)
        {
            _numericBase = basement;
        }

        public BigInteger(byte basement, List<byte> bi)
        {
            _numericBase = basement;
            this._binary.AddRange(bi);
        }

        public BigInteger(BigInteger ori)
        {
            _numericBase = ori._numericBase;
            this._binary.AddRange(ori._binary);
        }
        #endregion

        #region Method
        private BigInteger Extract(int index, int count)
        {
            BigInteger bigInt = new BigInteger(this._numericBase);
            List<byte> temp = this._binary.GetRange(index, count);
            bigInt._binary.AddRange(temp);
            return bigInt;
        }

        private void FillZero(int lenght)
        {
            if (this._binary.Count > lenght)
                return;
            for (int i = this._binary.Count; i < lenght; i++)
            {
                this._binary.Add((byte)0);
            }
        }

        private bool isZero()
        {
            for (int i = 0; i < this._binary.Count; i++)
                if (this._binary[i] != 0)
                    return false;
            return true;
        }

        private void Normalize()
        {
            int len = this._binary.Count;
            int f1i = -1;
            for (int i = len - 1; i >= 0; i--)
            {
                if (this._binary[i] == 1)
                {
                    f1i = i;
                    break;
                }
            }
            if (f1i == -1)
                return;
            if (f1i != len - 1)
            {
                this._binary.RemoveRange(f1i + 1, len - f1i - 1);
            }
        }
        #endregion

        #region Operator
        public static BigInteger operator +(BigInteger a, BigInteger b)
        {
            //a = (a0, a1,..., an), b = (b0, b1,... bn)
            BigInteger result = new BigInteger();
            byte numBase = a._numericBase;
            byte c = 0;
            int len = a._binary.Count >= b._binary.Count ? a._binary.Count : b._binary.Count;
            a.FillZero(len);
            b.FillZero(len);
            for (int i = 0; i < len; i++)
            {
                byte w = (byte)((a._binary[i] + b._binary[i] + c) % numBase);
                if ((byte)(a._binary[i] + b._binary[i] + c) < numBase)
                    c = 0;
                else
                    c = 1;
                result._binary.Add(w);
            }
            result._binary.Add(c);
            result.Normalize();
            a.Normalize();
            b.Normalize();
            return result;
        }

        public static BigInteger operator -(BigInteger a, BigInteger b)
        {
            //a = (a0, a1,..., an), b = (b0, b1,... bn)
            BigInteger result = new BigInteger();
            byte numBase = a._numericBase;
            int c = 0;
            int len = a._binary.Count >= b._binary.Count ? a._binary.Count : b._binary.Count;
            a.FillZero(len);
            b.FillZero(len);
            for (int i = 0; i < len; i++)
            {
                sbyte w = (sbyte)(a._binary[i] - b._binary[i] + c);
                if (w >= 0 && w < numBase)
                    c = 0;
                else
                    c = -1;

                if (w < 0)
                    w = (sbyte)(w + a._numericBase);
                byte res = (byte)w;
                result._binary.Add(res);
            }

            if (c < 0) //Negative __binary -> a < b
                result._binary.Add((byte)1);
            result.Normalize();
            a.Normalize();
            b.Normalize();
            return result;
        }

        public static BigInteger operator *(BigInteger a, BigInteger b)
        {
            //a = (a0, a1,..., an), b = (b0, b1,... bn)
            BigInteger result = new BigInteger();
            byte numBase = a._numericBase;
            int len = a._binary.Count >= b._binary.Count ? a._binary.Count : b._binary.Count;
            a.FillZero(len);
            b.FillZero(len);

            List<byte> temp = new List<byte>(len * 2);
            for (int i = 0; i < temp.Capacity; i++)
                temp.Add((byte)0);

            for (int i = 0; i < len; i++)
            {
                byte c = 0;
                for (int j = 0; j < len; j++)
                {
                    int uv = temp[i + j] + a._binary[j] * b._binary[i] + c;
                    BigInteger uvBi = BigIntegerManager.ConvertToBase_2(uv);
                    uvBi.FillZero(2);
                    temp[i + j] = uvBi._binary[0];
                    c = uvBi._binary[1];
                }
                temp[i + (len - 1) + 1] = c;
            }
            result._binary.AddRange(temp);
            result.Normalize();
            a.Normalize();
            b.Normalize();
            return result;
        }

        public static BigInteger operator /(BigInteger a, BigInteger b)
        {
            a.Normalize();
            b.Normalize();
            BigInteger aTemp = new BigInteger(a);
            BigInteger quotient = new BigInteger();
            List<byte> qt = new List<byte>();
            qt.Add((byte)0);
            int shift = aTemp._binary.Count - b._binary.Count;
            while (shift >= 0)
            {
                BigInteger temp = aTemp.Extract(shift, aTemp._binary.Count - shift);
                //temp.FromBigInteger(aTemp, shift, aTemp.__binary.Count - shift);

                if (temp >= b)
                {
                    aTemp._binary.RemoveRange(shift, aTemp._binary.Count - shift);
                    BigInteger h = temp - b;
                    aTemp._binary.AddRange(h._binary);
                    qt.Add((byte)1);
                }
                else
                {
                    qt.Add((byte)0);

                }
                shift--;
            }

            for (int i = qt.Count - 1; i >= 0; i--)
            {
                quotient._binary.Add(qt[i]);
            }
            quotient.Normalize();
            b.Normalize();
            return quotient;
        }

        public static BigInteger operator %(BigInteger a, BigInteger b)
        {
            BigInteger remainder = new BigInteger();
            BigInteger aTemp = new BigInteger(a);
            int shift = aTemp._binary.Count - b._binary.Count;
            while (shift >= 0)
            {
                BigInteger temp = aTemp.Extract(shift, aTemp._binary.Count - shift);
                //temp.FromBigInteger(aTemp, shift, aTemp.__binary.Count - shift);

                if (temp >= b)
                {
                    aTemp._binary.RemoveRange(shift, aTemp._binary.Count - shift);
                    BigInteger h = temp - b;
                    aTemp._binary.AddRange(h._binary);
                }
                shift--;
            }
            remainder._binary.AddRange(aTemp._binary);
            remainder.Normalize();
            a.Normalize();
            b.Normalize();
            return remainder;
        }

        public static int operator %(BigInteger a, int m)
        {
            int remain = 0;
            int x = 1;
            remain = a._binary[0] % m;
            for (int i = 1; i < a._binary.Count; i++)
            {
                x = (a._numericBase * x) % m;
                int z = (a._binary[i] * x) % m;
                remain = (remain + z) % m;
            }
            a.Normalize();
            return remain;
        }

        //em = x ^ this (mod m)
        public int ExponentMod_Base2(int x, int m)
        {
            int em = -1;
            if (this._numericBase == 2)
            {
                em = 1;
                if (this == 0)
                    return em;
                int a = x;
                if (this._binary[0] == 1)
                    em = x;
                for (int i = 1; i < this._binary.Count; i++)
                {
                    a = (a * a) % m;
                    if (this._binary[i] == 1)
                        em = (a * em) % m;
                }
            }
            return em;
        }

        public static bool operator <(BigInteger a, BigInteger b)
        {
            BigInteger sum = a - b;
            int len = a._binary.Count >= b._binary.Count ? a._binary.Count : b._binary.Count;
            if (sum._binary.Count > len) //sum is negative
                return true;
            return false;
        }

        public static bool operator >(BigInteger a, BigInteger b)
        {
            BigInteger sum = a - b;
            int len = a._binary.Count >= b._binary.Count ? a._binary.Count : b._binary.Count;
            if (sum._binary.Count <= len && !sum.isZero()) //sum is positive
                return true;
            return false;
        }

        public static bool operator <=(BigInteger a, BigInteger b)
        {
            BigInteger sum = a - b;
            int len = a._binary.Count >= b._binary.Count ? a._binary.Count : b._binary.Count;
            if (sum._binary.Count > len || sum.isZero()) //sum is negative
                return true;
            return false;
        }

        public static bool operator >=(BigInteger a, BigInteger b)
        {
            BigInteger sum = a - b;
            int len = a._binary.Count >= b._binary.Count ? a._binary.Count : b._binary.Count;
            if (sum._binary.Count <= len) //sum is positive or zero
                return true;
            return false;
        }

        public static bool operator ==(BigInteger a, BigInteger b)
        {
            BigInteger sum = a - b;
            int len = a._binary.Count >= b._binary.Count ? a._binary.Count : b._binary.Count;
            if (sum._binary.Count <= len && sum.isZero()) //sum is negative
                return true;
            return false;
        }

        public static bool operator !=(BigInteger a, BigInteger b)
        {
            BigInteger sum = a - b;
            if (!sum.isZero()) //sum is NOT zero
                return true;
            return false;
        }

        public static implicit operator BigInteger(int value)
        {
            BigInteger assigned = BigIntegerManager.ConvertToBase_2(value);
            return assigned;
        }

        public static explicit operator int(BigInteger a)
        {
            int dec = 0;
            int power = a._binary.Count - 1;
            for (int i = power; i >= 0; i--)
            {
                dec += a._binary[i] * (int)Math.Pow(2, i);
            }
            return dec;
        }

        public override string ToString()
        {
            String bb = "";
            for (int i = _binary.Count - 1; i >= 0; i--)
            {
                bb = String.Concat(bb, _binary[i].ToString());
            }
            return bb;
        }

        public override int GetHashCode()
        {
            return base.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        public static BigInteger Parse(String bin)
        {
            BigInteger res = new BigInteger();
            for (int i = bin.Length - 1; i >= 0; i--)
            {
                res._binary.Add(byte.Parse(bin[i].ToString()));
            }
            return res;

        }
        #endregion
    }

    public class BigIntegerManager
    {
        //Convert an integer to BigInteger
        public static BigInteger ConvertToBase_2(int m)
        {
            List<byte> temp = new List<byte>();
            int n = (int)(Math.Log10(m) / Math.Log10(2));
            for (int i = n; i >= 1; i--)
            {
                byte k = (byte)(m / Math.Pow(2, i));
                temp.Add(k);
                m -= k * (int)Math.Pow(2, i);
            }
            temp.Add((byte)m);
            temp.Reverse();
            BigInteger bigInt = new BigInteger(2, temp);
            return bigInt;

        }
    }
}
